package org.nowcoder.huawei.c100;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

/**
 * 65:构成制定长度字符串的个数
 */
public class HC065 {
    private static final LinkedList<Character> path = new LinkedList<>();
    private static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        String value = input[0];
        int n = Integer.parseInt(input[1]);
        boolean[] used = new boolean[value.length()];
        solve(value, n, used);
        System.out.println(count);
    }

    public static void solve(String value, int n, boolean[] used) {
        if (path.size() == n) {
            count++;
            return;
        }
        for (int i = 0; i < value.length(); i++) {
            //处理重复元素
            if (used[i]) {
                continue;
            }
            if (i > 0 && value.charAt(i) == value.charAt(i - 1) && !used[i - 1]) {
                continue;
            }
            path.add(value.charAt(i));
            used[i] = true;
            solve(value, n, used);
            path.removeLast();
            used[i] = false;
        }
    }
}
